19.6 複合的なスケジューリング : Tax-and-Spend
Tax-and-Spendがなぜ必要か
Metronomeはシングルプロセッサに限ってよく動作する
並列ガベージコレクションでないため
仕事ベースコレクタでは時間ベースコレクタに比べて桁違いに悪い遅延が発生する可能性がある
余裕ベーススケジューリングは周期的なアプリケーションにうまく適合するが、余裕がないような過負荷の状況では不安定
Tax-and-Spend
仕事ベースや余裕ベース、時間ベースを包含したアプローチ
Tax-and-Spendの基本動作
ミューテータが動くと、ミューテータ利用率と期間に応じて、コレクタの仕事を分担する
ミューテータに対する課税
ミューテータが動かないときはコレクタが仕事をする
コレクタによる貯金
この貯金によって将来のミューテータの分担を減らすことができる
発展的な課税
ミューテータ利用率と期間に応じて課税するのが基本
割り付け量やスレッドの実行時間、GC セーフポイントを通過した回数、実際の時間、仮想化された時間などに応じて課税することも可能
スレッド単位でメモリ割り付けの遅い実行経路（スレッドアロケーションバッファが溢れたとき）毎に保留されているコレクタの仕事があるか調べる
アロケートはできるだけスレッド単位でする
遅い経路とはグローバルなところからヒープをもらってくる挙動
このときにグローバルな情報にアクセスすれば無駄がない
グローバルな情報
GC セーフポイントを通過した回数
実際の時間
仮想化された時間
Tax-and-Spend スケジューリング
最小ミューテータ利用率はリアルタイム性の指標として便利
ここでのミューテータ利用率は、コレクタに課されるものではなく、アプリケーションの振る舞いから算出される指標を表している
GCの処理の時間粒度が応答性能よりも十分に小さい限り、システムのクロックにミューテータ利用率をかけたクロックでアプリケーションが動いていると捉えることができる
デッドラインのミスや病的に遅くなるケースもミューテータ利用率の変化で捉えることができる
Tax-and-Spend スケジューリングでは、スレッド毎に異なるミューテータ利用率を目標とすることができる
より高度なリアルタイム性が求められるスレッドに高いミューテータ利用率を割り振ることが可能
暇なプロセッサ上のバックグラウンドスレッドにGCの仕事をさせて(=貯金)、忙しいスレッドのミューテータ利用率を高める(=貯金を使って課税から逃れる)こともできる
スレッド毎のスケジューリング
Tax-and-Spendに必要な要件
コレクタの仕事をミューテータスレッドごとの尺度で見積もる
コレクタの仕事をスレッドごとに異なる程度で割り付ける
リアルタイム性の高いスレッドは少しだけ、暇なバックグラウンドスレッドはたくさん
コレクタに関する全ての作業はスレッド毎に計算できる
一つのスレッドがまとめて行う必要がある作業はない
OSに制御を戻さない
ミューテータスレッドは暇になってもOSに制御を戻さず、コレクタの仕事をする
そうでないと、ミューテータの仕事に応じた課税を支払うコレクタの仕事時間の分配をOSのスケジューラで行わざるをえない
スケジューラはミューテータと課税との対応がわかっていないので、勘違いどころか適切に分配することは不可能
当然無関係のスレッドをスケジュールしがち
スケジューラに任せず、ミューテータの中でコレクタの仕事をインターリーブすることでしか、適切な分量の課税を実現できない
これまでのスケジューリングの比較
ミューテータのメモリ割付に課税
(大量にメモリを割り付けると)最小ミューテータ利用率が悪化、停止時間もばらつく
そもそも余裕がないと性能が悪化する
負荷が大きいときも安定して動作するが
最小ミューテータ利用率が確保できればいつでもコレクタが発動する
コレクタに入力するパラメータが精確でなければならない
ここには書いてないが
仕事ベーススケジューリングと余裕ベーススケジューリングの組み合わせ
ミューテータごとに時間毎に払わなくてはならない税金の税率を設定する
税金 = コレクタの仕事
税率は最小ミューテータ使用率によって設定する
税金 = ミューテータの動いた時間 * (1 - 最小ミューテータ使用率)
余裕時間にはコレクタスレッドが仕事をして預金を積み上げる
コレクタスレッドの個数と優先度
コレクタスレッドはプロセッサの数だけ用意する
こうするとプロセッサの空き時間に自然とコレクタが走る
当然このコレクタスレッドがそれぞれ担当するプロセッサは固定のはず
コレクタスレッドには低いリアルタイムの優先度を与えるのが望ましい
リアルタイム > 低いリアルタイム > 通常
真のアイドルスレッドとして扱われることを避けることができ、他の実際の仕事を伴うスレッドと同等にスケジュールされる
真のアイドルスレッド
io待ちとか?
なぜ?
わからず
定期的にわずかにスリープするようにしておく
全プロセッサがコレクタスレッドで埋まってもリアルタイムでないプロセスが実行できる
税金はいつ払われるのか
ミューテータの実行中に納税期限が来ると、まず、そのミューテータは銀行から預金を引き出して支払おうとする
納税期限
最小ミューテータ利用率への到達
方法は書いてない
十分な預金がある
預金を使う
コレクタの仕事はしない
十分な預金がない
税金からその預金分を差し引く
預金を0にする
税金分のコレクタの仕事をする
Tax-and-Spend に必要な条件
インクリメンタルGC (required)
コレクタの仕事を仕事ベースの税金としてミューテータスレッドに課税したい
コレクタの仕事は細かく分割可能である必要がある
並行 GC (required)
ミューテータの仕事に余裕があるときに、並行してコレクタが実行できるように
並列 GC (optional)
複数のコレクタが同時に走る
ミューテータの中のコレクタとコレクタスレッドで走るメインコレクタが同時に走れる
並列できるとマルチプロセッサの性能が引き出せる
MetronomeからTax-and-Spendへの変更
コレクタの仕事はミューテータスレッドと並行して走るコレクタスレッドで行われる
並行GC
ミューテータスレッドがコレクタの仕事を実行できる
インクリメンタルかつ並列GC
並行 GC だけでは不十分
コレクタスレッドしかコレクタの仕事ができない
コレクタスレッドのスケジュールはOS
仕事に基づいたスケジュールが不可
スレッド間の同期プロトコル
「不揃いな時代」によるグローバルな合意
全てのスレッドで合意がほしいとき
「最後の 1 人」プロトコルによるフェーズの合意
あるフェーズを実行している全てのスレッドで合意がほしいとき
スレッド毎のコールバック
フェーズの終わりに何かしてほしいとき
「不揃いな時代」によるグローバルな合意
利用目的の例
コレクタの特定のフェーズでは、すべてのミューテータで特定のバリアが有効になっていなければならない
コレクションフェーズを終了させるためには、すべてのミューテータスレッドのローカルなストアバッファを書き出す必要がある
自分のスレッドがGCセーフポイントにおいて印をつけたタイミング以降に他のすべてのスレッドがGCセーフポイントを通過したかどうかを知るためのプロトコル
メカニズム
1 つの共有時代番号とスレッド毎のローカルな時代番号
共有時代番号は、新しい時代を始めるときに不可分にインクリメント
各スレッドは、共有時代からコピーすることで、自身のローカルな時代番号を更新する
各スレッドのローカルな時代番号は常に共有時代以下
どのスレッドからでも最も遅いローカル時代番号がわかるようにしておく
最も遅いローカル時代番号 = 確定時代
全部のスレッドのその時点でのローカル時代番号を取得してminをとる
タイミングはずれるかもしれないが、低めに見積もることはできる
全スレッドの間で一定の合意がとれたかどうかを知るために、「自分のスレッドが設定した時点での共有時代の値」と「今の確定時代の値」を比較する
自分のスレッドが次のフェーズに行きたいときに共有時代の値をインクリメントし、インクリメントした値を覚える
時系列の一例 (8スレッドの場合)
スレッドAが共有時代にN（=「あるスレッドが共有時代に設定した値」）を設定する
スレッドBが(GCセーフポイントに到達して)ローカル時代をNにする
スレッドCが共有時代にN+1を設定する
スレッドDがローカル時代をN+1にする
スレッドEがローカル時代をN+1にする
スレッドFが共有時代にN+2を設定する
スレッドBがローカル時代をN+2にする
スレッドGがローカル時代をN+2にする
スレッドHがローカル時代をN+2にする
このとき、スレッドA-Hのローカル時代はすべてN以上になった
論文をそのまま引用してみると
"Suppose thread A has performed some operation that establishes a new state of the memory management system (for example, it has enabled a store barrier that must be honored by all mutator threads during the next phase of the collection). Thread A then increments the global epoch and notes the result. Only when the confirmed epoch equals (or passes) this remembered value can A be certain that no thread is computing with a too-early view of the state (e.g., a view in which the store barrier is not enabled)."
スレッドAがある操作によって新しいフェーズへ移行するときを考える。例えば、そのフェーズでは全てのミューテータで特定のライトバリアが有効になっていなければならないとする。このとき、スレッドAは共有時代の値をインクリメントし、その結果を記憶する。スレッドAから見たとき、確定時代の値が記憶した値以上になっていれば、他のどのスレッドも次の状態、つまり特定のライトバリアが有効になっている状態に移っていると判断できる。
書かれていないが、各スレッドがローカルにどのフェーズにあるかというメタ情報が取得できるようになっているはずで、その情報が信頼できるタイミングを計るために共有時代と確定時代の比較を用いている
弱いメモリ順序のハードウェアでは、ローカルな時代を更新する前にメモリフェンスが必要
弱いメモリ順序 (p290)
すべての読み出し、書き込み、不可分操作が、システムのどの部分でも同じ順序で起きない
Aが
なにかやる（操作1） → ローカル時代を更新する（操作2）
Bが
Aのローカル時代を読む
Bから見ると操作1と操作2が逆転して見えることがある
I/O 待ちやネイティブコードの実行をしているスレッドについては、Tax-and-Spend では、時代に影響を受ける処理に戻る前に GC セーフポイントを実行してローカルな時代を更新することが要求される。そのため、これらのスレッドは常に現在の時代にいると考えることができ、これらのスレッドが追い付くのを待つ必要はない
I/O 待ちやネイティブコード実行中のスレッドはそもそも時代に影響を受ける処理を行っていない
そのスレッドが元の処理に戻るときには自分で時代に影響される処理（e.g. ライトバリア）を有効にしてから処理を開始する
なので待つ必要がない
「最後の 1 人」プロトコルによるフェーズの合意
「最後の 1 人」プロトコルの必要性
ミューテータスレッドを乗っ取って並行 GC を行う場合、ミューテータは課税されていて、コレクタの仕事をしている可能性がある
そして、コレクタの仕事の中にもマーク、スイープ、ファイナライズなどのフェーズがある
そのため、フェーズの検出をノンブロッキングで行うことが重要になる。
そうしなければ、課税されているミューテータはデッドラインをミスする可能性がある。
不揃いな時代はミューテータが課税されているかどうかを気にしないので、うまくいかない。
ある特定のフェーズで仕事をしているスレッド間で、その仕事が完全に終了した瞬間を合意するのには向かない？
不揃いな時代で実装すると？
グローバルキューに仕事が残っているかどうかと他のスレッドがローカルに仕事を抱えているかどうかとを知るタイミングが異なるので、本当に全体として仕事が残っているかを確定できない
無理やり実現しようとするとノンブロッキングでは難しい
「最後の 1 人」プロトコルの内容
フェーズ識別子とワーカのカウントを共有の不可分に更新できる領域に書き込む
最初ワーカのカウントは0である
税金を払うミューテータはワーカのカウントを1増やす
払い終えたら1減らす
このときワーカのカウントが0になればフェーズを進める
このカウントとフェーズの走査はアトミックに行う
「最後の1人」プロトコルを使ってノンブロッキングな納税を実装
スレッドが納税のタイムスライスを抜ける時には、やり残した仕事を常にグローバルなワークキューに戻す
やり残した仕事がなくなり、どれかのスレッドが最後のスレッドとなると次のフェーズに進む
最後のスレッドはワーカのカウントが0かつグローバルなワークキューの中身が0であるときだけフェーズを進める
「最後の 1 人」プロトコルが役に立たない場面
Metronome のマークフェーズの終了
Metronomeで使われる削除バリアは上書きされたポインタをスレッド毎の更新ログに保存する
マークフェーズの終了にはすべてのスレッドの更新ログが空になる必要がある
「最後の 1 人」プロトコルではすべてのスレッドの更新ログが空になったかどうかわからない
そのため Tax-and-Spend はファイナルマークフェーズを導入している
ファイナルマークフェーズでは、1 つのスレッドが残ったすべての仕事をし、不揃いな時代の仕組みを使ってすべての更新ログが空であるかどうかを確認する
更新ログが残っていれば並行マークへ戻る
スレッド毎のコールバック
いくつかのフェーズではすべてのミューテータが何かする/される必要がある
GC の最初のフェーズではすべてのミューテータのスタックを走査する必要がある
すべてのミューテータスレッドがスレッドローカルの状態を書き出して、コレクタから見えるようにする必要があるフェーズもある
コールバックプロトコル
あるマスタのコレクタスレッドが定期的にすべてのミューテータスレッドを監視し、必要なタスクを実行したかどうか調べる
まだ実行していないスレッドは、次の GC セーフポイントで必要なタスク（スタック走査やキャッシュフラッシュなど）をコールバック
I/O を待っていたりやネイティブコードを実行しているスレッドは、コレクタが代わりに実行し、I/O 待ちやネイティブコードから戻ることを禁止
禁止することになんの意味が?
ミューテータに戻ってしまうとスタックの走査結果がおかしくなる
したがって、どのスレッドでも、コールバックフェーズでの遅れは、最大でもタスクを実行するのにかかる時間で済む
進行性を保証するための優先度ブースト
ヒープを使い切る前にコレクションを終えなければならず、進行性が非常に重要
不揃いな時代、最後の 1 人、コールバックは、進行しなくなる可能性
高い優先度のスレッドの実行でプロセッサを使い切り、低いスレッドがプロトコルに応答できない場合
低優先度スレッドの優先度をそのスレッドが応答するまで一時的に引き上げる